package leetcode;

import java.util.ArrayList;
import java.util.List;

public class AddParentheses {

	//这道题没有思路，看的discuss
	//递归的思路，每当我们遇到运算符的时候，我们就分别计算两边的结果
	//然后对结果进行相应的计算
	//Runtime 7ms
	public List<Integer> diffWaysToCompute(String input) {
		List<Integer> res = new ArrayList<Integer>();
		if(input == null){
			return res;
		}
		int length = input.length();
		for(int i = 0; i < length; i++){
			char c = input.charAt(i);
			//如果c是运算符
			if (c == '-' || c == '+' || c == '*') {
				String a = input.substring(0, i);
				String b = input.substring(i + 1);
				List<Integer> al = diffWaysToCompute(a);
                List<Integer> bl = diffWaysToCompute(b);
                for (int x : al) {
                    for (int y : bl) {
                        if (c == '-') {
                            res.add(x - y);
                        } else if (c == '+') {
                            res.add(x + y);
                        } else if (c == '*') {
                            res.add(x * y);
                        }
                    }
                }
			}
		}
		//如果没有遇到任何运算符，我们需要将该数字加入
		if (res.size() == 0) res.add(Integer.valueOf(input));
		return res;
    }
	
	//dp 
	//动态规划与递归是有联系的，比如当我们知道递归的过程中只有与下标相关的变量在改变，而且结果是最优解或者唯一解
	//那么我们可以将该递归改写为动态规划，这样避免了函数的调用
	@SuppressWarnings("unchecked")
	public List<Integer> diffWaysToCompute_2(String input) {
		//dp[i][j] stores all possible results from the i-th integer to the j-th integer (inclusive) in the list
		List<Integer> res = new ArrayList<Integer>();
		if(input == null){
			return res;
		}
		int length = input.length();
		List<String> ops = new ArrayList<>();
		for (int i = 0; i < input.length(); i++) {
			int j = i;
			while (j < input.length() && Character.isDigit(input.charAt(j))){
				j++;
			}
			ops.add(input.substring(i, j));
			if (j != input.length()){
				ops.add(input.substring(j, j + 1));
			}
			i = j;
		}
		int N = (ops.size() + 1) / 2; // num of integers
		ArrayList<Integer>[][] dp = (ArrayList<Integer>[][]) new ArrayList[N][N];
		for (int d = 0; d < N; d++) {
			if (d == 0) {
				for (int i = 0; i < N; i++) {
					dp[i][i] = new ArrayList<>();
					dp[i][i].add(Integer.valueOf(ops.get(i * 2)));
				}
				continue;
			}
			for (int i = 0; i < N - d; i++) {
				dp[i][i + d] = new ArrayList<>();
				for (int j = i; j < i + d; j++) {
					ArrayList<Integer> left = dp[i][j], right = dp[j + 1][i + d];
					String operator = ops.get(j * 2 + 1);
					for (int leftNum : left)
						for (int rightNum : right) {
							if (operator.equals("+"))
								dp[i][i + d].add(leftNum + rightNum);
							else if (operator.equals("-"))
								dp[i][i + d].add(leftNum - rightNum);
							else
								dp[i][i + d].add(leftNum * rightNum);
						}
				}
			}
		}
		return dp[0][length - 1];
	}
}
